The read/write protocol complex is collapsible

摘要

The celebrated \emph{asynchronous computability theorem} provides acharacterization of the class of decision tasks that can be solved in await-free manner by asynchronous processes that communicate by writing andtaking atomic snapshots of a shared memory. Several variations of the modelhave been proposed (immediate snapshots and iterated immediate snapshots), allequivalent for wait-free solution of decision tasks, in spite of the fact thatthe protocol complexes that arise from the different models are structurallydistinct. The topological and combinatorial properties of these snapshotprotocol complexes have been studied in detail, providing explanations for whythe asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshotoperations. Instead, snapshots are implemented (by a wait-free protocol) usingoperations that write and read individual shared memory locations. Thus,read/write protocols are also computationally equivalent to snapshot protocols.However, the structure of the read/write protocol complex has not been studied.In this paper we show that the read/write iterated protocol complex iscollapsible (and hence contractible). Furthermore, we show that a distributedprotocol that wait-free implements atomic snapshots in effect is performing thecollapses.